package com.teng.algorithm.sort;

import java.util.Arrays;

/**
 * @author liangtl
 * @Date 2023/2/12
 * @Return
 * @Description: 冒泡排序的演进及最后代码
 */
public class BubbleSort {
    public static void main(String[] args) {
        int array[] = {3, 9, -1, 10, -2};

        // 以下为冒泡数组的演变过程：

        // 1、第一趟排序，将最大的数放置在最后一位
        int temp1;
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] > array[i + 1]) {
                temp1 = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp1;
            }
        }
        System.out.println("第一次排序后的结果为：" + Arrays.toString(array));

        // 2、第二趟排序，将第二大的数放在倒数第二位
        int temp2 = 0;
        for (int x = 0; x < array.length - 2; x++) {
            if (array[x] > array[x + 1]) {
                temp2 = array[x];
                array[x] = array[x + 1];
                array[x + 1] = temp2;
            }
        }
        System.out.println("第二次排序后的结果为：" + Arrays.toString(array));

        // 3、第三趟排序，将第三大的数放在倒数第三位
        int temp3;
        for (int y = 0; y < array.length - 3; y++) {
            if (array[y] > array[y + 1]) {
                temp3 = array[y];
                array[y] = array[y + 1];
                array[y + 1] = temp3;
            }
        }
        System.out.println("第三次排序后的结果为：" + Arrays.toString(array));

        // 4、第四趟排序，将第四大的数放在倒数第四位
        int temp4;
        for (int z = 0; z < array.length - 4; z++) {
            if (array[z] > array[z + 1]) {
                temp4 = array[z];
                array[z] = array[z + 1];
                array[z + 1] = temp4;
            }
        }
        System.out.println("第四次排序后的结果为：" + Arrays.toString(array));

        System.out.println("《==============分界线================》");

        // 冒泡排序
        int arr[] = {3, 9, -1, 10, -2};
        int temp;
        for (int m = 1; m <= arr.length - 1; m++) {
            for (int n = 0; n < arr.length - m; n++) {
                if (arr[n] > arr[n + 1]) {
                    temp = arr[n];
                    arr[n] = arr[n + 1];
                    arr[n + 1] = temp;
                }
            }
        }
        System.out.println("冒泡排序结果为：" + Arrays.toString(arr));

        /**
         * 冒泡排序优化
         * 情形：例如以上代码中，可能在第三次就已经完成了顺序排列，这样第四次的排序就是多余的，造成了资源浪费
         * 做法：添加一个标识符flag，判断在本次排序中是否发生过元素位置的变动，如果没有发生过，则说明已经达到了有序的情况
         */
        // 冒泡排序
        int arr_adv[] = {3, 9, -1, 10, -2};
        int temp_adv;
        boolean flag = false;
        for (int m = 1; m <= arr_adv.length - 1; m++) {
            for (int n = 0; n < arr_adv.length - m; n++) {
                if (arr_adv[n] > arr_adv[n + 1]) {
                    // 如果进来了这个循环，则说明会发生位置变动
                    flag = true;
                    temp_adv = arr_adv[n];
                    arr_adv[n] = arr_adv[n + 1];
                    arr_adv[n + 1] = temp_adv;
                }
            }
            // 如果flag为false，则说明没有进入n循环体，即元素位置没有发生变动，此时数组是有序序列，则可以退出m循环，否则重置flag进行下一次m循环
            if (!flag) {
                break;
            } else {
                flag = false;
            }
        }
        System.out.println("冒泡排序优化结果为：" + Arrays.toString(arr_adv));
    }
}
